<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  
  <title itemprop="name">图论 | Yuki_Blog</title>
  
    <link rel="shortcut icon" href="/images/favicon.ico">
  
  <meta http-equiv="x-dns-prefetch-control" content="on">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Noto+SerifMerriweather|Merriweather+Sans|Source+Code+Pro|Ubuntu:400,700|Noto+Serif+SC" media="all">
  <link rel="dns-prefetch" href="//cdn.jsdelivr.net">
  <link rel="stylesheet" id="saukra_css-css" href="/css/style.css" type="text/css" media="all">
  <link rel="stylesheet" href="/css/lib.min.css" media="all">
  <link rel="stylesheet" href="/css/font.css" media="all">
  <link rel="stylesheet" href="/css/insight.css" media="all">
  <link rel="stylesheet" href="/css/jquery.fancybox.min.css" media="all">
  <link rel="stylesheet" href="/css/zoom.css" media="all">
  <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<!--   <link rel="stylesheet" id="saukra_css-css" href="https://2heng.xin/wp-content/cache/autoptimize/css/autoptimize_ad42a61f4c7d4bdd9f91afcff6b5dda5.css
" type="text/css" media="all"> -->
  <script>
  /*Initial Variables*/
  var mashiro_option = new Object();
  var mashiro_global = new Object();
  mashiro_option.NProgressON = true;
  /* 
   * 邮箱信息之类的东西可以填在这里，这些js变量基本都作用于sakura-app.js
   * 这样的设置仅是为了方便在基于PHP开发的主题中设置js变量，既然移植到了Node上，我想或许可以精简这一逻辑吧
   */
  mashiro_option.email_domain = "";
  mashiro_option.email_name = "";
  mashiro_option.cookie_version_control = "";
  mashiro_option.qzone_autocomplete = false;
  mashiro_option.site_name = "YukiのBlog";
  mashiro_option.author_name = "Blog";
  mashiro_option.site_url = "https://kawaii-yuki.gitee.io";
  mashiro_option.v_appId = "kugxcpVLA8wXKraql2jEFO1r-gzGzoHsz";
  mashiro_option.v_appKey = "Le0otuGmt9RRFHunLbKL5Dj8";
  mashiro_option.mathjax = "0";
  mashiro_option.qq_api_url = "https://api.mashiro.top/qqinfo/"; 
  mashiro_option.qq_avatar_api_url = "https://api.mashiro.top/qqinfo/";

  // mashiro_option.jsdelivr_css_src = "https://cdn.jsdelivr.net/gh/moezx/cdn@3.4.5/css/lib.min.css";
  // mashiro_option.float_player_on = true;

  /*End of Initial Variables*/
  </script>
  <script type="text/javascript">
  var bg = "/images/cover/1.jpg".split(",");
  var bgindex = Math.floor(Math.random()*bg.length);
  if (!!window.ActiveXObject || "ActiveXObject" in window) { //is IE?
    alert('朋友，IE浏览器未适配哦~');
  }
  </script>
  <style type="text/css">
  .hljs-ln{border-collapse:collapse}.hljs-ln td{padding:0}.hljs-ln-n:before{content:attr(data-line-number)}
  </style>
  <style type="text/css">.site-top .lower nav{display:block !important;}.author-profile i,.post-like a,.post-share .show-share,.sub-text,.we-info a,span.sitename,.post-more i:hover,#pagination a:hover,.post-content a:hover,.float-content i:hover{color:#FE9600}.feature i,.download,.navigator i:hover,.links ul li:before,.ar-time i,span.ar-circle,.object,.comment .comment-reply-link,.siren-checkbox-radio:checked + .siren-checkbox-radioInput:after{background:#FE9600}::-webkit-scrollbar-thumb{background:#FE9600}.download,.navigator i:hover,.link-title,.links ul li:hover,#pagination a:hover,.comment-respond input[type='submit']:hover{border-color:#FE9600}.entry-content a:hover,.site-info a:hover,.comment h4 a,#comments-navi a.prev,#comments-navi a.next,.comment h4 a:hover,.site-top ul li a:hover,.entry-title a:hover,#archives-temp h3,span.page-numbers.current,.sorry li a:hover,.site-title a:hover,i.iconfont.js-toggle-search.iconsearch:hover,.comment-respond input[type='submit']:hover{color:#FE9600}.comments .comments-main{display:block !important;}.comments .comments-hidden{display:none !important;}background-position:center center;background-attachment:inherit;}
  </style>
<meta name="generator" content="Hexo 5.4.0"></head>

<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/sakura.js"></script>
<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/noSomeKey.js"></script>
<script src="https://cdn.jsdelivr.net/gh/wallleap/cdn/js/canvas-nest.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>
<body class="page-template page-template-user page-template-page-analytics page-template-userpage-analytics-php page page-id-1297 chinese-font serif isWebKit">
  <div class="scrollbar" id="bar">
  </div>
  <a href="#" class="cd-top faa-float animated"></a>
  <section id="main-container">
    <div class="headertop filter-dot">
  <div id="banner_wave_1"></div>
  <div id="banner_wave_2"></div>
  <figure id="centerbg" class="centerbg">
    <div class="focusinfo no-select">
      <div class="header-tou">
        <a target="_blank" rel="noopener" href="https://kawaii-yuki.gitee.io">
          <img src="/images/avatar.jpg">
        </a>
      </div>
      <div class="header-info">
        <p>有我有你 一鼓作气</p>
        <div class="top-social_v2">
          <li id="bg-pre">
            <img class="flipx" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
          
            
              
                <li>
                  <a href="https://github.com/sukixj" target="_blank" class="social-github" title="github">
                    <img src="/images/social/github.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://space.bilibili.com/42429348" target="_blank" class="social-github" title="bilibili">
                    <img src="/images/social/bilibili.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://weibo.com/u/2396685637" target="_blank" class="social-github" title="sina">
                    <img src="/images/social/sina.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://music.163.com/#/user/home?id=1754519629" target="_blank" class="social-github" title="wangyiyun">
                    <img src="/images/social/wangyiyun.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="https://www.zhihu.com/people/you-xi-sama-74" target="_blank" class="social-github" title="zhihu">
                    <img src="/images/social/zhihu.png">
                  </a>
                </li>
              
            
              
                <li>
                  <a href="" target="_blank" class="social-github" title="email">
                    <img src="/images/social/email.svg">
                  </a>
                </li>
              
            
              
                <li class="wechat">
                  <a href="/#">
                    <img src="/images/social/wechat.png">
                  </a>
                  <div class="wechatInner">
                    <img src="/images/wechat.png">
                  </div>
                </li>
              
            
          
          <li id="bg-next">
            <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/next-b.svg">
          </li>
        </div>
      </div>
    </div>
  </figure>
  <div id="video-container" style="">
    <video style="object-fit: fill" id="bgvideo" class="video" video-name="" src="" width="auto" preload="auto">
    </video>
    <div id="video-btn" class="loadvideo videolive">
    </div>
    <div id="video-add">
    </div>
    <div class="video-stu">
    </div>
  </div>
  <div class="headertop-down faa-float animated" onclick="headertop_down()">
    <span>
      <i class="fa fa-chevron-down" aria-hidden="true">
      </i>
    </span>
  </div>
</div>
    <div id="page" class="site wrapper">
      <header class="site-header no-select gizle sabit" role="banner">
  <div class="site-top">
    <div class="site-branding">
      <span class="site-title">
        <span class="logolink moe-mashiro">
          <a href="/">
            <span class="sakurasono">Yukiの</span>
            <span class="shironeko">Blog</span>
          </a>
        </span>
      </span>
    </div>
    <div class="searchbox search-form-submit">
      <i class="iconfont js-toggle-search iconsearch icon-search">
      </i>
    </div>
    <div id="show-nav" class="showNav mobile-fit">
      <div class="line line1">
      </div>
      <div class="line line2">
      </div>
      <div class="line line3">
      </div>
    </div>
    <div class="lower-cantiner">
      <div class="lower">
        <nav class="mobile-fit-control hide">
          <ul id="menu-new" class="menu">
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
                    首页
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/archives">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
                    归档
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/categories/%E6%8A%80%E6%9C%AF/">
                          <i class="fa fa-code" aria-hidden="true"></i>
                          技术
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E7%94%9F%E6%B4%BB/">
                          <i class="fa fa-file-text-o" aria-hidden="true"></i>
                          生活
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%B5%84%E6%BA%90/">
                          <i class="fa fa-cloud-download" aria-hidden="true"></i>
                          资源
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E9%9A%8F%E6%83%B3/">
                          <i class="fa fa-commenting-o" aria-hidden="true"></i>
                          随想
                        </a>
                      </li>
                    
                      <li>
                        <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                          <i class="fa fa-book" aria-hidden="true"></i>
                          转载
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="javascript:;">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
                    清单
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/tags/%E6%82%A6%E8%AF%BB/">
                          <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                          书单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/bangumi/">
                          <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                          番组
                        </a>
                      </li>
                    
                      <li>
                        <a href="/music/">
                          <i class="fa fa-headphones" aria-hidden="true"></i>
                          歌单
                        </a>
                      </li>
                    
                      <li>
                        <a href="/tags/%E5%9B%BE%E9%9B%86/">
                          <i class="fa fa-photo" aria-hidden="true"></i>
                          图集
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/comment/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
                    留言板
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/links/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
                    友人帐
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/donate/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
                    赞赏
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
                    关于
                  </span>
                </a>
                
                  <ul class="sub-menu">
                    
                      <li>
                        <a href="/about/">
                          <i class="fa fa-meetup" aria-hidden="true"></i>
                          我？
                        </a>
                      </li>
                    
                      <li>
                        <a href="/theme-sakura/">
                          <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                          主题
                        </a>
                      </li>
                    
                      <li>
                        <a href="/lab/">
                          <i class="fa fa-cogs" aria-hidden="true"></i>
                          Lab
                        </a>
                      </li>
                    
                  </ul>
                
              </li>
            
              <li>
                <a href="/client/">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-android faa-vertical" aria-hidden="true"></i>
                    客户端
                  </span>
                </a>
                
              </li>
            
              <li>
                <a href="/atom.xml">
                  <span class="faa-parent animated-hover">
                    <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
                    RSS
                  </span>
                </a>
                
              </li>
            
          </ul>
        </nav>
      </div>
    </div>
  </div>
</header>

      <link rel="stylesheet" type="text/css" href="/css/sharejs.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.css">
<div class="pattern-center-blank"></div>

  <div class="pattern-center single-center">
    <!-- 有配图默认渲染第一张 -->
    <div class="pattern-attachment-img lazyload" style="background-image: url(https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg);" src="" data-src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg">
    </div>
    <header class="pattern-header single-header">
      <h1 class="entry-title">
      图论</h1>
      <p class="entry-census">
        <span>
          <a href="">
            <img src="">
          </a>
        </span>
        <span>
          <a href=""></a>
        </span>
        <span class="bull">
        ·</span>
        2017-10-19<span class="bull">
        ·</span>
      <span id="busuanzi_value_page_pv"></span>次阅读</p>
    </header>
  </div>

<div id="content" class="site-content">
  <div id="primary" class="content-area">
    <main id="main" class="site-main" role="main">
      <article id="post-1" class="post-1 post type-post status-publish format-standard has-post-thumbnail hentry category-uncategorized">
        <div class="toc"></div>
        <!--<div class="toc-entry-content"><!-- 套嵌目录使用（主要为了支援评论）-->
        
        <div class="entry-content">
          <h2 id="图的存储"><a href="#图的存储" class="headerlink" title="图的存储"></a>图的存储</h2><h3 id="邻接矩阵"><a href="#邻接矩阵" class="headerlink" title="邻接矩阵"></a>邻接矩阵</h3><ul>
<li><strong>map[i][j] 表示第 i 个点与第 j 个点连有一条边，如有权值就把矩阵内元素的值赋成权值。空间复杂度O（n2），时间复杂度O（n2）</strong><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> Adjacency <span class="title">matrix</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> u,v,c;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;u,&amp;v,&amp;c);</span><br><span class="line">		map[u][v]=c;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++) &#123;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>
<h3 id="邻接表"><a href="#邻接表" class="headerlink" title="邻接表"></a>邻接表</h3><ul>
<li><strong>使用vector存储，开n个vector，每个代表一个节点，它后面的数就是这个节点能连向哪个节点。空间复杂度会因为不会扫到没有用的边而降到O（m）</strong><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> Adjacency <span class="title">list</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	vector &lt;<span class="keyword">int</span>&gt; ve[MAXN];</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> u,v,c;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;u,&amp;v,&amp;c);</span><br><span class="line">		ve[u].<span class="built_in">push_back</span>(v);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=ve[i].<span class="built_in">size</span>();j++) &#123;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>
<h3 id="边表（前向星）"><a href="#边表（前向星）" class="headerlink" title="边表（前向星）"></a>边表（前向星）</h3><ul>
<li><p><strong>边表是图的一种存储结构，用来描述图上的每一个点。对图的每个边进行编号，对图的每个顶点建立一个链表（n个顶点建立n个链表），第i个容器中的结点包含以顶点Vi为起点的所有边的编号。</strong>  </p>
</li>
<li><p><strong>边表与邻接表的区别：边表存储了以点为起点的边的信息，邻接表存储了以点为出发点的点的信息。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Edge</span> &#123;</span></span><br><span class="line">    <span class="keyword">int</span> nxt,to,cost;</span><br><span class="line">&#125;e[MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v,<span class="keyword">int</span> w)</span> </span>&#123;</span><br><span class="line">    num++;</span><br><span class="line">    e[num].to=v;</span><br><span class="line">    e[num].cost=w;</span><br><span class="line">    e[num].nxt=head[u];</span><br><span class="line">    head[u]=num;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++) &#123;</span><br><span class="line">        <span class="keyword">int</span> u,v,w;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d%d%d&quot;</span>,&amp;u,&amp;v,&amp;w);</span><br><span class="line">        <span class="built_in">insert</span>(u,v,w);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].nxt) &#123;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>
<hr>
<h2 id="最短路问题"><a href="#最短路问题" class="headerlink" title="最短路问题"></a>最短路问题</h2><h3 id="Dijkstra"><a href="#Dijkstra" class="headerlink" title="Dijkstra"></a>Dijkstra</h3><p>&emsp;&emsp;迪杰斯特拉算法是由荷兰计算机科学家Dijkstra于1959 年提出的，因此又叫Dijkstra算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。  </p>
<p><strong>时间复杂度为O（n2），不能处理存在负边权的情况，求单源最短路。</strong></p>
<ul>
<li><p><strong>算法实现：</strong></p>
<p><strong>每次找到一个能到达的最近的点，来更新到达其他点的距离。</strong><br>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oJXTANUD-1612685862988)(<a target="_blank" rel="noopener" href="http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)]">http://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)]</a></p>
</li>
</ul>
<p><strong>设起点为s，dis[v]表示从s到v的最短路径，pre[v]为v的前驱节点，用来输出路径。</strong>    </p>
<p>初始化：dis[v]=∞(v≠s); dis[s]=0; pre[s]=0; </p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n ; i++)</span><br><span class="line">          <span class="number">1.</span>在没有被访问过的点中找一个顶点u使得dis[u]是最小的。</span><br><span class="line">          <span class="number">2.u</span>标记为已确定最短路径</span><br><span class="line">          <span class="number">3.f</span><span class="keyword">or</span> 与u相连的每个未确定最短路径的顶点v</span><br><span class="line">            <span class="keyword">if</span>  (dis[u]+w[u][v] &lt; dis[v])  &#123;</span><br><span class="line">                dis[v] = dis[u] + w[u][v];</span><br><span class="line">                pre[v] = u;</span><br><span class="line">             &#125;</span><br></pre></td></tr></table></figure>
<ul>
<li><p><strong>算法结束：</strong> </p>
<p><strong>dis[v]为s到v的最短距离；pre[v]为v的前驱节点，用来输出路径。</strong></p>
</li>
<li><p><strong>代码实现：</strong></p>
</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> <span class="keyword">int</span>  MAXINT = <span class="number">32767</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXNUM = <span class="number">10</span>;</span><br><span class="line"><span class="keyword">int</span> dist[MAXNUM];</span><br><span class="line"><span class="keyword">int</span> prev[MAXNUM];</span><br><span class="line"><span class="keyword">int</span> A[MAXUNM][MAXNUM];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Dijkstra</span><span class="params">(<span class="keyword">int</span> v0)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">bool</span> S[MAXNUM];                                  <span class="comment">// 判断是否已存入该点到S集合中</span></span><br><span class="line">	<span class="keyword">int</span> n=MAXNUM;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;=n; ++i) &#123;</span><br><span class="line">		dist[i] = A[v0][i];</span><br><span class="line">		S[i] = <span class="literal">false</span>;                                <span class="comment">// 初始都未用过该点</span></span><br><span class="line">		<span class="keyword">if</span>(dist[i] == MAXINT)</span><br><span class="line">			prev[i] = <span class="number">-1</span>;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			prev[i] = v0;</span><br><span class="line">		　　</span><br><span class="line">	&#125;</span><br><span class="line">	dist[v0] = <span class="number">0</span>;</span><br><span class="line">	S[v0] = <span class="literal">true</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>; i&lt;=n; i++) &#123;</span><br><span class="line">		<span class="keyword">int</span> mindist = MAXINT;</span><br><span class="line">		<span class="keyword">int</span> u = v0;             </span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>; j&lt;=n; ++j)						<span class="comment">// 找出当前未使用的点j的dist[j]最小值</span></span><br><span class="line">	        <span class="keyword">if</span>((!S[j]) &amp;&amp; dist[j]&lt;mindist) &#123;</span><br><span class="line">		        u = j;                              <span class="comment">// u保存当前邻接点中距离最小的点的号码</span></span><br><span class="line">				mindist = dist[j];		　　</span><br><span class="line">			&#125;</span><br><span class="line">		S[u] = <span class="literal">true</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>; j&lt;=n; j++)</span><br><span class="line">			<span class="keyword">if</span>((!S[j]) &amp;&amp; A[u][j]&lt;MAXINT) &#123;</span><br><span class="line">				<span class="keyword">if</span>(dist[u] + A[u][j] &lt; dist[j]) &#123;   <span class="comment">//在通过新加入的u点路径找到离v0点更短的路径</span></span><br><span class="line">				    dist[j] = dist[u] + A[u][j];    <span class="comment">//更新dist</span></span><br><span class="line">					prev[j] = u;                    <span class="comment">//记录前驱顶点	　　</span></span><br><span class="line">				&#125;	　    　</span><br><span class="line">			&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="Floyd"><a href="#Floyd" class="headerlink" title="Floyd"></a>Floyd</h3><p>&emsp;&emsp;Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授Robert W·Floyd命名。   </p>
<p><strong>时间复杂度O（n3）,可以处理所有图，多源最短路。</strong></p>
<ul>
<li><p><strong>算法实现：</strong><br><strong>假设有三个点 i,j,k，i连向 j，i 连向 k，k 连向 j，i 到 j 的最短路就是 i 到 j 的路径和 i 到 k 的路径加 k 到 j 的路径和较短的那个。</strong></p>
</li>
<li><p><strong>代码实现：</strong>  </p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">floyd</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="built_in">memset</span>(dist,<span class="number">0x3f</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(dist));</span><br><span class="line">	<span class="built_in">memset</span>(map,<span class="number">0x3f</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(map));</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=n;k++) </span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n;j++) &#123;</span><br><span class="line">		dist[i][j]=<span class="built_in">min</span>(map[i][j],map[i][k]+map[k][j]);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="SPFA"><a href="#SPFA" class="headerlink" title="SPFA"></a>SPFA</h3><p>&emsp;&emsp;我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。</p>
</li>
<li><p><strong>优化：</strong><br><strong>SPFA算法有两个优化策略SLF和LLL——SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)&lt;=x，则将i出队进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。</strong>  </p>
</li>
<li><p><strong>代码实现：</strong>  </p>
<p>  <strong>1.判断负环：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">   <span class="function"><span class="keyword">int</span> <span class="title">spfa_dfs</span><span class="params">(<span class="keyword">int</span> u)</span> </span>&#123;</span><br><span class="line">	vis[u]=<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> k=f[u]; k!=<span class="number">0</span>; k=e[k].next) &#123;</span><br><span class="line">		<span class="keyword">int</span> v=e[k].v,w=e[k].w;</span><br><span class="line">		<span class="keyword">if</span>(dis[u]+w&lt;dis[v]) &#123;</span><br><span class="line">			dis[v]=dis[u]+w;</span><br><span class="line">			<span class="keyword">if</span>(!vis[v]) &#123;</span><br><span class="line">				<span class="keyword">if</span>(<span class="built_in">spfa_dfs</span>(v))</span><br><span class="line">					<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">			&#125; <span class="keyword">else</span></span><br><span class="line">				<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	vis[u]=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;<strong>2.一般SPFA：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">spfa</span><span class="params">(<span class="keyword">int</span> s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=<span class="number">10010</span>;i++)dist[i]=<span class="number">2147483647</span>;</span><br><span class="line">    queue&lt;<span class="keyword">int</span>&gt; q;</span><br><span class="line">    dist[s]=<span class="number">0</span>;</span><br><span class="line">    vis[s]=<span class="number">1</span>;</span><br><span class="line">    q.<span class="built_in">push</span>(s);</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">        <span class="keyword">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        vis[u]=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].next) &#123;</span><br><span class="line">            <span class="keyword">int</span> to=e[i].to;</span><br><span class="line">            <span class="keyword">if</span>(dist[to]&gt;dist[u]+e[i].cost) &#123;</span><br><span class="line">                dist[to]=dist[u]+e[i].cost;</span><br><span class="line">                <span class="keyword">if</span>(!vis[to]) &#123;</span><br><span class="line">                    vis[to]=<span class="number">1</span>;</span><br><span class="line">                    q.<span class="built_in">push</span>(to);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;<strong>SLF优化：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">spfa</span><span class="params">(<span class="keyword">int</span> s)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">fill</span>(dis,dis+n+<span class="number">1</span>,<span class="number">2147483647</span>);</span><br><span class="line">    deque &lt;<span class="keyword">int</span>&gt; q;</span><br><span class="line">    dis[s]=<span class="number">0</span>;</span><br><span class="line">    vis[s]=<span class="number">1</span>;</span><br><span class="line">    q.<span class="built_in">push_back</span>(s);</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">        <span class="keyword">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop_front</span>();</span><br><span class="line">        vis[u]=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].nxt) &#123;</span><br><span class="line">            <span class="keyword">int</span> to=e[i].to;</span><br><span class="line">            <span class="keyword">if</span>(dis[to]&gt;dis[u]+e[i].cost) &#123;</span><br><span class="line">                dis[to]=dis[u]+e[i].cost;</span><br><span class="line">                <span class="keyword">if</span>(!vis[to]) &#123;</span><br><span class="line">                    vis[to]=<span class="number">1</span>;</span><br><span class="line">                    <span class="keyword">if</span>(!q.<span class="built_in">empty</span>() &amp;&amp; dis[to]&lt;dis[q.<span class="built_in">front</span>()]) q.<span class="built_in">push_front</span>(to);</span><br><span class="line">                    <span class="keyword">else</span> q.<span class="built_in">push_back</span>(to);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;<strong>SLF + LLL优化:</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">spfa</span><span class="params">(<span class="keyword">int</span> s)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">fill</span>(dis,dis+n+<span class="number">1</span>,<span class="number">2147483647</span>);</span><br><span class="line">    deque &lt;<span class="keyword">int</span>&gt; q;</span><br><span class="line">    <span class="keyword">int</span> tot=<span class="number">1</span>,sum=<span class="number">0</span>;</span><br><span class="line">    dis[s]=<span class="number">0</span>;</span><br><span class="line">    vis[s]=<span class="number">1</span>;</span><br><span class="line">    q.<span class="built_in">push_back</span>(s);</span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">        <span class="keyword">int</span> u=q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop_front</span>();</span><br><span class="line">        <span class="keyword">if</span>(dis[u]*tot&gt;sum) &#123;</span><br><span class="line">            q.<span class="built_in">push_back</span>(u);</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        tot--;</span><br><span class="line">        sum-=dis[u];</span><br><span class="line">        vis[u]=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=head[u];i;i=e[i].nxt) &#123;</span><br><span class="line">            <span class="keyword">int</span> to=e[i].to;</span><br><span class="line">            <span class="keyword">if</span>(dis[to]&gt;dis[u]+e[i].cost) &#123;</span><br><span class="line">                dis[to]=dis[u]+e[i].cost;</span><br><span class="line">                <span class="keyword">if</span>(!vis[to]) &#123;</span><br><span class="line">                    vis[to]=<span class="number">1</span>;</span><br><span class="line">                    tot++;</span><br><span class="line">                    sum+=dis[to];</span><br><span class="line">                    <span class="keyword">if</span>(!q.<span class="built_in">empty</span>() &amp;&amp; dis[to]&lt;dis[q.<span class="built_in">front</span>()]) q.<span class="built_in">push_front</span>(to);</span><br><span class="line">                    <span class="keyword">else</span> q.<span class="built_in">push_back</span>(to);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>
<hr>
<h2 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h2><p>&emsp;&emsp;<strong>如果存在一个排列a1,a2,…,an，使得在该图中不存在ai到aj的路径(i&gt;j)，我们称这个排列为这个图的拓扑序列。我们每次寻找入度为 0 的点加入序列中。并将当前点连接的所有边均删除，更新其它点的度数。由于每条边至多被删除一次。因此这个时间复杂度是 O(|E|) 的。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">topsort</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	queue&lt;<span class="keyword">int</span>&gt;q;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) <span class="keyword">if</span>(du[i]==<span class="number">0</span>) q.<span class="built_in">push</span>(i);</span><br><span class="line">	<span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">		now=q.<span class="built_in">front</span>();</span><br><span class="line">		q.<span class="built_in">pop</span>();</span><br><span class="line">		k++;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=p[now]; i!=<span class="number">-1</span>; i=e[i].next) &#123;</span><br><span class="line">			go=e[i].to;</span><br><span class="line">			du[go]--;</span><br><span class="line">			<span class="keyword">if</span>(du[go]==<span class="number">0</span>)</span><br><span class="line">				q.<span class="built_in">push</span>(go);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(k==n) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2><p>&emsp;&emsp;<strong>字面意思，可供合并和查找的集合。常用于判断两个点是否联通。</strong><br>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8sPDVPUc-1612685862992)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2Hmo6.png)]">https://s3.ax1x.com/2020/12/24/r2Hmo6.png)]</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(fa[x]!=x) <span class="keyword">return</span> fa[x]=<span class="built_in">find</span>(fa[x]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;</span><br><span class="line">	fa[<span class="built_in">find</span>(x)]=fa[<span class="built_in">find</span>(y)];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<hr>
<h2 id="二分图"><a href="#二分图" class="headerlink" title="二分图"></a>二分图</h2><p>&emsp;&emsp;<strong>如果一个无向图G中V能分成两个点集A与B，且位于A中的顶点互相之间没有边，位于B中的顶点互相之间没有边，则称这个图为二分图。</strong>  </p>
<ul>
<li><p><strong>二分图染色：（判断是否为二分图）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">vector &lt;<span class="keyword">int</span>&gt; v[N];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">  col[x]=y;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;v[x].<span class="built_in">size</span>(); i++)</span><br><span class="line">  &#123;</span><br><span class="line">     <span class="keyword">if</span> (!col[v[x][i]]) <span class="built_in">dfs</span>(v[x][i],<span class="number">3</span>-y);</span><br><span class="line">     <span class="keyword">if</span> (col[v[x][i]]==col[x]) FLAG=<span class="literal">true</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">color</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=n; i++) col[i]=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=n; i++) <span class="keyword">if</span> (!col[i]) <span class="built_in">dfs</span>(i,<span class="number">1</span>);</span><br><span class="line">	<span class="keyword">if</span> (FLAG) cout&lt;&lt;<span class="string">&quot;NO&quot;</span>; <span class="keyword">else</span> cout&lt;&lt;<span class="string">&quot;YES&quot;</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>col[i]=1 i这个点染成黑色 col[i]=2 i这个点染成白色 col[i]=0 i这个点还未被染色</p>
</li>
<li><p><strong>裂点：</strong></p>
<p>首先明确：<strong>二分图不存在奇环。</strong><br><strong>将每个点A裂成两个点A与A’。<br>若A与B之间存在边，则连一条A与B’的边，A’与B的边。<br>若此时A与A’连通，或者B与B’连通，则该图不是二分图。（若连通则必然出现了奇环）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> f[k]==k?f[k]:f[k]=<span class="built_in">find</span>(f[k]);</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=n; i++) p[i][<span class="number">0</span>]=++cnt,p[i][<span class="number">1</span>]=++cnt;</span><br><span class="line"><span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=cnt; i++) f[i]=i;</span><br><span class="line"><span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=m; i++) &#123;</span><br><span class="line">	<span class="comment">// u-v</span></span><br><span class="line">	f[<span class="built_in">find</span>(p[u][<span class="number">0</span>])]=<span class="built_in">find</span>(p[v][<span class="number">1</span>]);</span><br><span class="line">	f[<span class="built_in">find</span>(p[u][<span class="number">1</span>])]=<span class="built_in">find</span>(p[v][<span class="number">0</span>]);</span><br><span class="line">	<span class="keyword">if</span> (<span class="built_in">find</span>(p[u][<span class="number">0</span>])==<span class="built_in">find</span>(p[u][<span class="number">1</span>]) || <span class="built_in">find</span>(p[v][<span class="number">0</span>])==<span class="built_in">find</span>(p[v][<span class="number">1</span>])) FLAG=<span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">if</span> (FLAG) <span class="built_in">puts</span>(<span class="string">&quot;NO&quot;</span>);</span><br><span class="line"><span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">&quot;YES&quot;</span>);</span><br></pre></td></tr></table></figure>
<h2 id="二分图最大匹配"><a href="#二分图最大匹配" class="headerlink" title="二分图最大匹配"></a>二分图最大匹配</h2></li>
<li><p><strong>匈牙利算法</strong>  </p>
<p><strong>顾名思义，在一个二分图中选择最多的边，使得没有任何一个点有连接它的两条边被选择到。</strong>   </p>
<p>例如：有四个男生，四个女生，每个男生都对几个女生有好感，我们的目标是满足尽量多的男生的要求。  </p>
</li>
</ul>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gUUnW3oq-1612685862994)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2Hqk6.png)]">https://s3.ax1x.com/2020/12/24/r2Hqk6.png)]</a>  </p>
<p>&emsp;<strong>1.先给1号男生找女生，找到了女1号。</strong>  </p>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d4ncEDPn-1612685862997)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2bV1g.png)]">https://s3.ax1x.com/2020/12/24/r2bV1g.png)]</a>  </p>
<p>&emsp;<strong>2.给2号男生找女生，找到了女2号。</strong>  </p>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xaU0bQ4F-1612685862999)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2bTgg.png)]">https://s3.ax1x.com/2020/12/24/r2bTgg.png)]</a>  </p>
<p>&emsp;<strong>3.给3号男生找女生，找到女1号，先抢了试试。</strong>  </p>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-59eHYSHB-1612685863000)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2bbuj.png)]">https://s3.ax1x.com/2020/12/24/r2bbuj.png)]</a>  </p>
<p>&emsp;<strong>4.1号男生没了女生，找下一个，找到女2号，抢了！</strong>  </p>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JCEvUEcp-1612685863001)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2bv5V.png)]">https://s3.ax1x.com/2020/12/24/r2bv5V.png)]</a>  </p>
<p>&emsp;<strong>5.2号男生没了女生，找到了女3号！</strong>  </p>
<p>[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gzdCnRHa-1612685863002)(<a target="_blank" rel="noopener" href="https://s3.ax1x.com/2020/12/24/r2qS8U.png)]">https://s3.ax1x.com/2020/12/24/r2qS8U.png)]</a>  </p>
<p>&emsp;<strong>6.给4号男生找女生，发现无论如何也做不到不拆散别人的情况下给他分配一个女生了。</strong>  </p>
<p><strong>用递归实现上述过程：</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> now)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> a=<span class="number">1</span>; a&lt;=m; a++)</span><br><span class="line">		<span class="keyword">if</span> (match[now][a] &amp;&amp; !use[a]) &#123;</span><br><span class="line">			use[a]=<span class="literal">true</span>;</span><br><span class="line">			<span class="keyword">if</span> (!result[a] || <span class="built_in">dfs</span>(result[a])) &#123;</span><br><span class="line">				result[a]=now;</span><br><span class="line">				<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">xiongyali</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> a=<span class="number">1</span>; a&lt;=n; a++) &#123;</span><br><span class="line">		<span class="built_in">memset</span>(use,<span class="literal">false</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(use));</span><br><span class="line">		<span class="keyword">if</span> (<span class="built_in">dfs</span>(a)) ans++;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>&emsp;<strong>如果让你求一个答案答案一定在 ans , n - ans , m - ans , n + m - ans 之中。</strong></p>
<hr>
<hr>
<h1 id="最小生成树"><a href="#最小生成树" class="headerlink" title="- 最小生成树"></a>- 最小生成树</h1><p><strong>一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。</strong></p>
<ul>
<li><h2 id="Kruskal"><a href="#Kruskal" class="headerlink" title="Kruskal"></a>Kruskal</h2></li>
</ul>
<p><strong>思想：贪心的去寻找最短的边，然后用并查集维护。</strong><br><strong>稀疏图Kruskal跑的飞快，时间复杂度大约O（nlogn）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">comp</span><span class="params">(E a,E b)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a.v&lt;b.v;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(fa[x]!=x) <span class="keyword">return</span> fa[x]=<span class="built_in">find</span>(fa[x]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;</span><br><span class="line">	fa[<span class="built_in">find</span>(x)]=fa[<span class="built_in">find</span>(y)];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Kruskal</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) fa[i]=i;</span><br><span class="line">	<span class="built_in">sort</span>(e+<span class="number">1</span>,e+<span class="number">1</span>+m,comp);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,k=<span class="number">0</span>;i&lt;=m;i++) &#123;</span><br><span class="line">		<span class="keyword">if</span>(<span class="built_in">find</span>(e[i].x) != <span class="built_in">find</span>(e[i].y)) &#123;</span><br><span class="line">			<span class="built_in">merge</span>(e[i].x,e[i].y);</span><br><span class="line">			k++;</span><br><span class="line">			tot+=e[i].v;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(k == n<span class="number">-1</span>) &#123;</span><br><span class="line">			cout&lt;&lt;tot;</span><br><span class="line">			<span class="keyword">return</span> ;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	cout&lt;&lt;<span class="string">&quot;orz&quot;</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<hr>
<h1 id="强连通分量"><a href="#强连通分量" class="headerlink" title="强连通分量"></a>强连通分量</h1><p><strong>简单来说强联通分量就是同一个图中能够互相联通的几个点。可以实现图的缩点。</strong></p>
<ul>
<li><h2 id="Tarjan"><a href="#Tarjan" class="headerlink" title="Tarjan"></a>Tarjan</h2></li>
</ul>
<p><strong>思想：以DFS为基础，我们定义DFN[x]为搜索到x时的时间戳（即搜索到的时间）。LOW[x]为搜索树中x以及它的子孙可以访问到的最早祖先。有LOW[x]=min(DFN[x],DFN[j],LOW[k])，其中存在边(x,j)，(x,k)，j为x的祖先，k为x的子孙。令v[i]表示i是否已被搜索过以及是否找到了极大强连通分量。若i已经找到了极大强连通分量或者还未被搜索过，则v[i]=0，否则v[i]=1。</strong></p>
<p><strong>①找到一个未被搜索过的节点u，若不存在，退出，否则以这个节点为根开始建立搜索树。</strong></p>
<p><strong>②给该节点建立时间戳，将x压入栈中，枚举该节点的所有儿子x，若其儿子没被访问过，则搜索其儿子（重复②），之后更新LOW[u]=min(LOW[u],LOW[x])，否则若v[x]=1(表示x是u的祖先)，则更新LOW[u]=min(LOW[u],DFN[x])。</strong></p>
<p><strong>③对u搜索完毕后，若LOW[u]=DFN[u]，则找到了一个极大强连通分量，栈顶到u都为一个极大强连通分量。更新v与栈。</strong></p>
<ul>
<li><h3 id="代码实现："><a href="#代码实现：" class="headerlink" title="代码实现："></a>代码实现：</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	DFN[x]=++Time;</span><br><span class="line">	LOW[x]=DFN[x];</span><br><span class="line">	st[++r]=x;</span><br><span class="line">	<span class="keyword">int</span> R=r;</span><br><span class="line">	V[x]=<span class="literal">true</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;v[x].<span class="built_in">size</span>(); i++)</span><br><span class="line">		<span class="keyword">if</span> (v[x][i]!=fa[x]) &#123;</span><br><span class="line">			fa[v[x][i]]=x;</span><br><span class="line">			<span class="keyword">if</span> (!DFN[v[x][i]]) &#123;</span><br><span class="line">				<span class="built_in">dfs</span>(v[x][i]);</span><br><span class="line">				LOW[x]=<span class="built_in">min</span>(LOW[x],LOW[v[x][i]]);</span><br><span class="line">			&#125; <span class="keyword">else</span> <span class="keyword">if</span> (V[v[x][i]]) LOW[x]=<span class="built_in">min</span>(LOW[x],DFN[v[x][i]]);</span><br><span class="line">		&#125;</span><br><span class="line">	<span class="keyword">if</span> (LOW[x]==DFN[x]) &#123;</span><br><span class="line">		cnt++;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i=R; i&lt;=r; i++) &#123;</span><br><span class="line">			p[st[i]]=cnt;</span><br><span class="line">			V[st[i]]=<span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		r=R<span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>
<p><strong>cnt 第cnt个极大强联通分量  p[i]  i所处的是哪个极大强联通分量<br>LOW[x]==DFN[x]  已出现一个极大强联通分量</strong></p>
<p>缩点：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (i=<span class="number">1</span>; i&lt;=m; i++)</span><br><span class="line">	<span class="keyword">if</span> (p[u[i]]!=p[v[i]])</span><br><span class="line">		<span class="built_in">merge</span>(p[u[i]],p[v[i]]);</span><br></pre></td></tr></table></figure>
<hr>
<h1 id="最近公共祖先（LCA）"><a href="#最近公共祖先（LCA）" class="headerlink" title="- 最近公共祖先（LCA）"></a>- 最近公共祖先（LCA）</h1><p><strong>Lowest Common Ancestors，对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。</strong></p>
<ul>
<li><h2 id="离线算法-Tarjan"><a href="#离线算法-Tarjan" class="headerlink" title="离线算法 Tarjan"></a>离线算法 Tarjan</h2><del>没写过。</del></li>
</ul>
<p><strong>在一次遍历中把所有询问一次性解决，时间复杂度是O(n+q)。</strong></p>
<h4 id="算法流程："><a href="#算法流程：" class="headerlink" title="算法流程："></a>算法流程：</h4><p><strong>1.任选一个点为根节点，从根节点开始。</strong></p>
<p><strong>2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。</strong></p>
<p><strong>3.若是v还有子节点，返回2，否则下一步。</strong></p>
<p><strong>4.合并v到u上。</strong></p>
<p><strong>5.寻找与当前点u有询问关系的点v。</strong></p>
<p><strong>6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。</strong></p>
<p><strong>遍历的话需要用到dfs来遍历，至于合并，最优化的方式就是利用并查集来合并两个节点。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;tree[x].<span class="built_in">size</span>();++i) &#123;</span><br><span class="line">		<span class="built_in">tarjan</span>(tree[x][i]);</span><br><span class="line">		<span class="built_in">merge</span>(x,tree[x][i]);</span><br><span class="line">		anc[<span class="built_in">find</span>(x)] = x;</span><br><span class="line">	&#125;</span><br><span class="line">	vis[x] = <span class="literal">true</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;query[x].<span class="built_in">size</span>();++i) &#123;</span><br><span class="line">		<span class="keyword">if</span>(vis[query[x][i]])</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;the LCA for %d and %d is %d\n&quot;</span>, x, query[x][i], anc[<span class="built_in">find</span>(query[x][i])]);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li><h2 id="在线算法-倍增"><a href="#在线算法-倍增" class="headerlink" title="在线算法 倍增"></a>在线算法 倍增</h2></li>
</ul>
<p><strong>找最近公共祖先这问题很容易想到让两节点一起往上走最后相遇，但这样的dfs显然很慢，于是就需要倍增。就是用二进制的思维，以1,2,4,8等2的阶层步长接近答案，比一步一步向上要快很多。<br>所以要dfs出来点的2^k的父亲节点与该节点的深度。<br>找lca时先将下面的点升到与另一点同一深度，再用往上倍增找lca。<br>有两种大同小异的方法：一种是以上一步2倍长的步伐向上试，不行再缩减，找到一个离lca能达到的最近点。另一种是先求出最大深度是2的几次方，再以当前最大步伐向上走。</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lca</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(deep[x]&gt;deep[y]) <span class="built_in">swap</span>(x,y);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">20</span>; i&gt;=<span class="number">0</span>; i--) &#123;</span><br><span class="line">		<span class="keyword">if</span>(deep[fa[y][i]]&gt;=deep[x]) y=fa[y][i];   </span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(x==y)<span class="keyword">return</span> x;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">20</span>; i&gt;=<span class="number">0</span>; i--) &#123;</span><br><span class="line">		<span class="keyword">if</span>(fa[x][i]!=fa[y][i]) &#123;</span><br><span class="line">			x=fa[x][i],y=fa[y][i];   </span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> fa[x][<span class="number">0</span>];</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	deep[x]=deep[fa[x][<span class="number">0</span>]]+<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>; fa[x][i]; i++)</span><br><span class="line">		fa[x][i+<span class="number">1</span>]=fa[fa[x][i]][i];</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;vec[x].<span class="built_in">size</span>(); i++)</span><br><span class="line">		<span class="keyword">if</span>(!deep[vec[x][i]]) &#123;</span><br><span class="line">			fa[vec[x][i]][<span class="number">0</span>]=x;   </span><br><span class="line">			<span class="built_in">dfs</span>(vec[x][i]);</span><br><span class="line">		&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li><h2 id="树剖"><a href="#树剖" class="headerlink" title="树剖"></a>树剖</h2></li>
</ul>
<p>size[x]为以x为结点的子树的结点的个数 每个结点和它的儿子之间只有一条重边，这个重边连向它的儿子中size最大的那个儿子。<br>如果结点u和它的儿子v之间是一条轻边，那么<br>size[v] * 2&lt;size[u]。<br>top[i]记录i结点所在链的链头，如果top[u]!=top[v]说明u v不在一条链上 将 u=fa[u]，重复上述操作；当它们在一条链上时，深度较小的那个点为他们的lca。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	size[x]=<span class="number">1</span>;</span><br><span class="line">	deep[x]=deep[fa[x]]+<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;vec[x].<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span>(fa[x]!=vec[x][i]) &#123;</span><br><span class="line">			fa[vec[x][i]]=x;</span><br><span class="line">			<span class="built_in">dfs</span>(vec[x][i]);</span><br><span class="line">			size[x]+=size[vec[x][i]];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Get_heavy_edge</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> s=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>(!top[x]) top[x]=x;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;vec[x].<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span>(fa[x]!=vec[x][i]&amp;&amp;size[vec[x][i]]&gt;size[s])s=vec[x][i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(s) &#123;</span><br><span class="line">		top[s]=top[x];</span><br><span class="line">		<span class="built_in">Get_heavy_edge</span>(s);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>; i&lt;vec[x].<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span>(fa[x]!=vec[x][i]&amp;&amp;vec[x][i]!=s) <span class="built_in">Get_heavy_edge</span>(vec[x][i]);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lca</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(; top[x]!=top[y];) &#123;</span><br><span class="line">		<span class="keyword">if</span>(deep[top[x]]&lt;deep[top[y]]) <span class="built_in">swap</span>(x,y);</span><br><span class="line">		x=fa[top[x]];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(deep[x]&gt;deep[y]) <span class="built_in">swap</span>(x,y);</span><br><span class="line">	<span class="keyword">return</span> x;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<hr>

        </div>
        <!-- .entry-content -->
        <div class="single-reward">
          <div class="reward-open">赏
            <div class="reward-main">
              <ul class="reward-row">
                <li class="alipay-code"><img src="/images/donate/AliPayQR.jpg"></li>
                <li class="wechat-code"><img src="/images/donate/WeChanQR.jpg"></li>
              </ul>
            </div>
          </div>
        </div>
        <div style="text-align:center; width: 100%" class="social-share share-mobile" data-disabled="diandian, tencent"></div>
        <footer class="post-footer">
          <div class="post-lincenses"><a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="nofollow"><i class="fa fa-creative-commons" aria-hidden="true"></i> 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议</a></div>
          <div class="post-tags">
          </div>
          <div class="post-share">
            <div class="social-share sharehidden share-component"></div>
            <i class="iconfont show-share icon-forward"></i>
          </div>
        </footer><!-- .entry-footer -->
      </article>
      <!-- #post-## -->
      <div class="toc" style="background: none;"></div>
      <section class="post-squares nextprev">
        
          
            <div class="post-nepre full previous">
          
            <a href="/2017/10/20/datastructure/" rel="prev">
              <div class="background">
                <img class="lazyload" src="" data-src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg" style="width: 100%; height: 100%; object-fit: cover; pointer-events: none;" onerror="imgError(this,3)" src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.4/img/banner/comment.jpg">
              </div>
              <span class="label">
              Previous Post</span>
              <div class="info">
                <h3>
                数据结构</h3>
                <hr>
              </div>
            </a>
          </div>
        
        
      </section>
      
<div id="vcomments"></div>
<script>
  window.onload = function(){
      var valine = new Valine();
      valine.init({
        el: '#vcomments',
        appId: "kugxcpVLA8wXKraql2jEFO1r-gzGzoHsz",
        appKey: "Le0otuGmt9RRFHunLbKL5Dj8",
        path: window.location.pathname,
        placeholder: "你是我一生只会遇见一次的惊喜 ..."
      })
  }
</script>

      <section class="author-profile">
        <div class="info" itemprop="author" itemscope="" itemtype="https://schema.org/Person">
          <a href="" class="profile gravatar"><img src="" itemprop="image" alt="" height="70" width="70"></a>
          <div class="meta">
            <span class="title">Author</span>
            <h3 itemprop="name">
            <a href="" itemprop="url" rel="author"></a>
            </h3>
          </div>
        </div>
        <hr>
        <p><i class="iconfont icon-write"></i></p>
      </section>
    </main><!-- #main -->
  </div><!-- #primary -->
</div>



    </div>    
    <div class="ins-search">
    <div class="ins-search-mask"></div>
    <div class="ins-search-container">
        <div class="ins-input-wrapper">
            <input type="text" class="ins-search-input" placeholder="请输入关键词..."/>
            <span class="ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            // PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
        },
        ROOT_URL: '/',
        CONTENT_URL: '/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
    <!-- <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2021 Yuki<br>
      powered_by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer> -->
<footer id="colophon" class="site-footer" role="contentinfo">
  <div class="site-info">
    <div class="footertext">
      <div class="img-preload">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/wordpress-rotating-ball-o.svg">
        <img src="https://cdn.jsdelivr.net/gh/honjun/cdn@1.6/img/other/disqus-preloader.svg">
      </div>
      <p style="color: #666666;">&copy 2018</p>
    </div>
    <div class="footer-device">
    <p style="font-family: 'Ubuntu', sans-serif;">
        <span style="color: #b9b9b9;">Theme <a href="https://github.com/honjun/hexo-theme-sakura" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Sakura</a> <i class="iconfont icon-sakura rotating" style="color: #ffc0cb;display:inline-block"></i> by <a href="https://2heng.xin/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Mashiro</a>&<a href="https://www.hojun.cn/" target="_blank" style="color: #b9b9b9;;text-decoration: underline dotted rgba(0, 0, 0, .1);">Hojun</a>, Powered by Hexo, Hosted by Coding Pages</a>
        </span>
      </p>
    </div>
  </div><!-- .site-info -->
</footer>



<!-- <script src="/js/tocbot.js"></script> -->
<script type="text/javascript" src="/js/lib.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script type="text/javascript" src="/js/InsightSearch.js"></script>
<script type="text/javascript" src="/js/jquery.fancybox.min.js"></script>
<script type="text/javascript" src="/js/zoom.min.js"></script>
<script type="text/javascript" src="/js/sakura-app.js"></script>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='//unpkg.com/valine@1.3.4/dist/Valine.min.js'></script>
<script src="/js/botui.js"></script>
<!-- 不蒜子 网页计数器 -->
<script src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<!-- <script src="https://cdnjs.cloudflare.com/ajax/libs/tocbot/4.4.2/tocbot.min.js"></script> -->
<script type="text/javascript">
/* <![CDATA[ */
if (/Android|webOS|iPhone|iPod|BlackBerry/i.test(navigator.userAgent)) {
  var Poi = {"pjax":"1","movies":{"url": "","name":"Unbroken.mp4","live":"close"},"windowheight":"fixed","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
} else {
  var Poi = {"pjax":"1","movies":{"url": "","name":"Unbroken.mp4","live":"open"},"windowheight":"auto","codelamp":"close","ajaxurl":"","order":"asc","formpostion":"bottom"};
}
/* ]]> */

</script>
<script>
$(document).ready(function() {
  if ($(".toc").length > 0 && document.body.clientWidth > 1200) {
    if ($(".pattern-center").length > 0) { //有图的情况
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -400,
          scrollSmoothOffset: -85
      });
    } else {
      tocbot.init({
          // Where to render the table of contents.
          tocSelector: '.toc', // 放置目录的容器
          // Where to grab the headings to build the table of contents.
          contentSelector: '.entry-content', // 正文内容所在
          // Which headings to grab inside of the contentSelector element.
          scrollSmooth: true,
          headingSelector: 'h1, h2, h3, h4, h5', // 需要索引的标题级别
          headingsOffset: -85,
          scrollSmoothOffset: -85
      });
    }
    var offsetTop = $('.toc').offset().top - 95;
    window.onscroll = function() {
      var scrollTop = window.pageYOffset || document.documentElement.scrollTop || document.body.scrollTop;
      if (scrollTop >= offsetTop) {
        $('.toc').addClass('toc-fixed');
      } else {
        $('.toc').removeClass('toc-fixed');
      }
    }
  }
});
</script>

    <div class="openNav no-select" style="height: 50px;">
      <div class="iconflat no-select" style="width: 50px; height: 50px;">
        <div class="icon"></div>
      </div>
      <div class="site-branding search-form-submit">
        <i class="iconfont js-toggle-search iconsearch icon-search"></i>
      </div>
    </div>
  </section>
  <div id="mo-nav" class="">
  <div class="m-avatar">
    <img src="/images/avatar.jpg">
  </div>
  <p style="text-align: center; color: #333; font-weight: 900; font-family: 'Ubuntu', sans-serif; letter-spacing: 1.5px">YukiのBlog</p>
  <p style="text-align: center; word-spacing: 20px;">
    
      
        <a href="https://github.com/sukixj" class="fa fa-github" target="_blank" style="color: #333; margin-left:20px"></a>
      
        <a href="https://weibo.com/u/2396685637" class="fa fa-weibo" target="_blank" style="color: #dd4b39; margin-left:20px"></a>
      
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=uytBaS8dNXwkPgV_ZxWO_kTG5fruS0va&noverify=0" class="fa fa-qq" target="_blank" style="color: #25c6fe; margin-left:20px"></a>
      
    
  </p>
  <ul id="menu-new-1" class="menu">
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-fort-awesome faa-shake" aria-hidden="true"></i>
            首页
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/archives">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-archive faa-shake" aria-hidden="true"></i>
            归档
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/categories/%E6%8A%80%E6%9C%AF/">
                  <i class="fa fa-code" aria-hidden="true"></i>
                  技术
                </a>
              </li>
            
              <li>
                <a href="/categories/%E7%94%9F%E6%B4%BB/">
                  <i class="fa fa-file-text-o" aria-hidden="true"></i>
                  生活
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%B5%84%E6%BA%90/">
                  <i class="fa fa-cloud-download" aria-hidden="true"></i>
                  资源
                </a>
              </li>
            
              <li>
                <a href="/categories/%E9%9A%8F%E6%83%B3/">
                  <i class="fa fa-commenting-o" aria-hidden="true"></i>
                  随想
                </a>
              </li>
            
              <li>
                <a href="/categories/%E8%BD%AC%E8%BD%BD/">
                  <i class="fa fa-book" aria-hidden="true"></i>
                  转载
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="javascript:;">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-list-ul faa-vertical" aria-hidden="true"></i>
            清单
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/tags/%E6%82%A6%E8%AF%BB/">
                  <i class="fa fa-th-list faa-bounce" aria-hidden="true"></i>
                  书单
                </a>
              </li>
            
              <li>
                <a href="/bangumi/">
                  <i class="fa fa-film faa-vertical" aria-hidden="true"></i>
                  番组
                </a>
              </li>
            
              <li>
                <a href="/music/">
                  <i class="fa fa-headphones" aria-hidden="true"></i>
                  歌单
                </a>
              </li>
            
              <li>
                <a href="/tags/%E5%9B%BE%E9%9B%86/">
                  <i class="fa fa-photo" aria-hidden="true"></i>
                  图集
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/comment/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-pencil-square-o faa-tada" aria-hidden="true"></i>
            留言板
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/links/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-link faa-shake" aria-hidden="true"></i>
            友人帐
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/donate/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-heart faa-pulse" aria-hidden="true"></i>
            赞赏
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-leaf faa-wrench" aria-hidden="true"></i>
            关于
          </span>
        </a>
        
          <ul class="sub-menu">
            
              <li>
                <a href="/about/">
                  <i class="fa fa-meetup" aria-hidden="true"></i>
                  我？
                </a>
              </li>
            
              <li>
                <a href="/theme-sakura/">
                  <i class="fa iconfont icon-sakura" aria-hidden="true"></i>
                  主题
                </a>
              </li>
            
              <li>
                <a href="/lab/">
                  <i class="fa fa-cogs" aria-hidden="true"></i>
                  Lab
                </a>
              </li>
            
          </ul>
        
      </li>
    
      <li>
        <a href="/client/">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-android faa-vertical" aria-hidden="true"></i>
            客户端
          </span>
        </a>
        
      </li>
    
      <li>
        <a href="/atom.xml">
          <span class="faa-parent animated-hover">
            <i class="fa  fa-rss faa-pulse" aria-hidden="true"></i>
            RSS
          </span>
        </a>
        
      </li>
    
  </ul>
  <p style="text-align: center; font-size: 13px; color: #b9b9b9;">&copy 2019 hexo-sakura</p>
</div>
<button onclick="topFunction()" class="mobile-cd-top" id="moblieGoTop" title="Go to top" style="display: none;"><i class="fa fa-chevron-up" aria-hidden="true"></i></button>
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css">
<script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script>
<!-- require MetingJS -->
<script src="https://cdn.jsdelivr.net/npm/meting@2/dist/Meting.min.js"></script>
<style>
  .aplayer .aplayer-lrc {
    height: 35px;
  }
  .aplayer .aplayer-lrc p{
    font-size: 16px;
    font-weight: 700;
    line-height: 18px !important;
  }
  .aplayer .aplayer-lrc p.aplayer-lrc-current{
    color: #FF1493;
  }
  .aplayer.aplayer-narrow .aplayer-body{
    left: -66px !important;
  }
  .aplayer.aplayer-fixed .aplayer-lrc {
    display: none;
  }
  .aplayer .aplayer-lrc.aplayer-lrc-hide {
      display:none !important;
  }
  .aplayer.aplayer-fixed .lrc-show {
    display: block;
    background: rgba(255, 255, 255, 0.8);
  }
</style>
<meting-js

    id="2660651585"

    server="netease"

    type="playlist"

    fixed="true"

    autoplay="false"

    loop="all"

    order="random"

    preload="auto"

    volume="0.7"

    mutex="true"

</meting-js>
<script>
  $(function(){
    $('body').on('click', '.aplayer', function(){
      if($('.aplayer-button').hasClass('aplayer-play')) {
        $('.aplayer-lrc').removeClass('lrc-show');
      } else {
        $('.aplayer-lrc').addClass('lrc-show');
      }
    })
  });
</script>
  
</body>
</html>